package Array.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      给定一个非负整数数组A，A 中一半整数是奇数，一半整数是偶数。
 *      对数组进行排序，以便当A[i]为奇数时，i也是奇数；当A[i]为偶数时，i也是偶数。
 *
 * 2. 算法分析
 *
 *
 * 3，代码实现
 */
@SuppressWarnings("all")
public class 按奇偶排序数组2 {
    // 空间复杂度高，不推荐的写法，但是思路简单，如果数据量比较小可以使用，但是不建议
    public int[] sortArrayByParityII1(int[] A) {
        int n = A.length;
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for(int x : A) {
            if(x % 2 == 0) {
                even.add(x);
            } else {
                odd.add(x);
            }
        }
        int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            if(i % 2 == 0) {
                res[i] = even.get(i / 2);
            } else {
                res[i] = odd.get(i / 2);
            }
        }
        return res;
    }

    // 优化
    public int[] sortArrayByParityII2(int[] A) {
        int n = A.length;
        int[] res = new int[n];
        // 偶数索引放置偶数
        // 奇数索引放置奇数
        int i = 0;
        int j = 1;
        for(int x : A) { // 扫描A中所有元素
            if(x % 2 == 0 && i < n) {
                // 如果为偶数
                res[i] = x;
                i += 2;
            } else if(j < n){
                // 如果为奇数
                res[j] = x;
                j += 2;
            }
        }
        return res;
    }
}
